package likouJava;

import java.util.ArrayList;
import java.util.List;

public class 分割回文串 {

    List<List<String>> res = new ArrayList<>();
    List<String>path = new ArrayList<>();
    public List<List<String>> partition(String s) {
       backtrack(s, 0);
       return res;
    }

    private void backtrack(String s, int start) {
        if (start == s.length()){
            res.add(new ArrayList<>(path));
            return;
        }
        //枚举切割
        for (int end = start; end < s.length(); end++) {
            if (isPalindrome(s, start, end)){
                path.add(s.substring(start, end + 1));
                backtrack(s, end + 1);
                path.remove(path.size() - 1);
            }
        }

    }

    private boolean isPalindrome(String s, int l, int r) {
        while ( l < r){
            if (s.charAt(l++) != s.charAt(r--))return false;
        }
        return true;
    }

}
